// 排序问题：
// 输入： n个数的一个序列 (a_1, a_2, ..., a_n)
// 输出：输出序列的一个排列 (a_1^', a_2^', a_n^')，满足 a_1^' <= a_2^' <= ... <= a_n^'。
pub fn insertion_sort<T: PartialOrd + Clone>(a: &mut [T]) {
    for j in 1..a.len() {
        let key = a[j].clone();
        let mut i = (j as isize) - 1;
        while i >= 0 && a[i as usize] > key {
            a[i as usize + 1] = a[i as usize].clone();
            i -= 1;
        }
        a[(i + 1) as usize] = key;
    }
}

mod tests {
    #[test]
    fn insertion_sort() {
        use super::insertion_sort;
        use crate::test_utils;
        let mut a = test_utils::gen_random_vec::<i32>(100);
        insertion_sort(a.as_mut_slice());
        test_utils::assert_vec_asc(&a);
    }
}
